#include <iostream>
using namespace std;
#include <vector>
#include <unordered_map>

//class Solution {
//public:
//    int findMin(vector<int>& nums) {
//        int left = 0;
//        int right = nums.size() - 1;
//        int x = nums[right];
//        while (left < right)
//        {
//            int mid = (left + right) / 2;
//            if (nums[mid] < x)
//            {
//                right = mid;
//            }
//            else
//            {
//                left = mid + 1;
//            }
//        }
//        return nums[left];
//    }
//};
//
//int main() {
//    vector<long long> p;
//    vector<long long> pp;
//    pp.push_back(0);
//    int n = 0;
//    int q = 0;
//    cin >> n >> q;
//    long long nums = 0;
//    while (n--)
//    {
//        long long num;
//        cin >> num;
//        p.push_back(num);
//        nums += num;
//        pp.push_back(nums);
//    }
//    while (q--)
//    {
//        int l, r;
//        cin >> l >> r;
//        cout << pp[r] - pp[l - 1] << endl;
//    }
//    return 0;
//}
//
//int main() {
//    int n, m, q;
//    cin >> n >> m >> q;
//    vector<vector<int>> v1(n + 1, vector<int>(m + 1));
//    for (int x = 1; x <= n; x++)
//    {
//        for (int y = 1; y <= m; y++)
//        {
//            cin >> v1[x][y];
//        }
//    }
//    vector<vector<long long>> v2(n + 1, vector<long long>(m + 1));
//    for (int x = 1; x <= n; x++)
//    {
//        for (int y = 1; y <= m; y++)
//        {
//            v2[x][y] = v2[x - 1][y] + v2[x][y - 1] + v1[x][y] - v2[x - 1][y - 1];
//        }
//    }
//    int x1 = 0;
//    int x2 = 0;
//    int y1 = 0;
//    int y2 = 0;
//    while (q--)
//    {
//        cin >> x1 >> y1 >> x2 >> y2;
//        cout << v2[x2][y2] - v2[x1 - 1][y2] - v2[x2][y1 - 1] + v2[x1 - 1][y1 - 1] << endl;
//    }
//    return 0;
//}

//class Solution {
//public:
//    int pivotIndex(vector<int>& nums) {
//        int n = nums.size();
//        vector<long long> ret(n + 1);
//        for (int i = 1; i <= n; i++)
//        {
//            ret[i] = ret[i - 1] + nums[i - 1];
//        }
//        for (int i = 1; i <= n; i++)
//        {
//            if (ret[i - 1] == ret[n] - ret[i])
//            {
//                return i - 1;
//            }
//        }
//        return -1;
//    }
//};
//
//int main()
//{
//    Solution s;
//    vector<int> v = { 1, 7, 3, 6, 5, 6 };
//    s.pivotIndex(v);
//    return 0;
//}

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> ret;
        int n = nums.size();
        int sum = 1;
        int p = 0;
        for (int i = 0; i < n; i++)
        {
            if (nums[i] == 0)
            {
                p++;
                if (p > 2)
                {
                    sum = 0;
                    break;
                }
                continue;
            }
            sum *= nums[i];
        }
        for (int i = 0; i < n; i++)
        {
            if (p == 1 && nums[i] == 0)
            {
                ret.push_back(sum);
            }
            else if (p > 1)
            {
                ret.push_back(0);
            }
            else if (p == 1 && nums[i] != 0)
            {
                ret.push_back(0);
            }
            else
            {
                ret.push_back(sum / nums[i]);
            }
        }
        return ret;
    }
};

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> ret;
        vector<int> f(n);
        vector<int> g(n);
        f[0] = g[n - 1] = 1;
        for (int i = 1; i < n; i++)
        {
            f[i] = f[i - 1] * nums[i - 1];
        }
        for (int i = n - 2; i >= 0; i--)
        {
            g[i] = g[i + 1] * nums[i + 1];
        }
        for (int i = 0; i < n; i++)
        {
            ret.push_back(g[i] * f[i]);
        }
        return ret;
    }
};

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        hash[0] = 1;
        int sum = 0;
        int ret = 0;
        for (auto s : nums)
        {
            sum += s;
            if (hash.count(sum - k))
            {
                ret += hash[sum - k];
            }
            hash[sum]++;
        }
        return ret;
    }
};